As shown in FIG. 1, routers such as router 20 have a route processor 22 and a forwarding engine 24. The route processor 22 communicates with other routers 26, 28, 30 in a network to obtain updates of route information regarding the network. A route processor 22 maintains a routing table 32 which contains a large number of entries for use by the router 20 to determine how to forward packets that are received by the router. Conventional routing tables 32 may contain hundreds of thousands of elements, and as a greater number of devices such as personal data assistants (PDAs), cell phones, and other devices are assigned IP addresses, the number of entries in a routing table 32 is expected to grow substantially over the coming years.
The forwarding engine 24 of a router 20 has a forwarding table 34 containing routing information obtained from the route processor 22. The forwarding engine 24 accesses its forwarding table 34 during a lookup process performed by the forwarding engine 24 to determine the next hop or next destination of a packet being processed by the router 20.
When the route/processor 22 receives a new route from another router 26, 28, or 30 in the network and updates its routing table 32 information to reflect the new route data, the route processor 22 passes the new route information to the forwarding engine 24 so that the appropriate changes may be made in the forwarding table 34. In conventional routers, the entire routing table 32 may be copied into the forwarding table 34 of the forwarding engine.
As recognized by the present inventors, what is needed is a method for reducing the number of entries in a forwarding table while maintaining the proper forwarding information to make correct forwarding decisions.
It is against this background that various embodiments of the present invention were developed.